package com.heima.algorithm.recursion;

import java.util.Arrays;

/**
 * <h2>斐波拉契数列</h2>
 * 0,1,1,2,3,5,8,13,21……
 */
public class Fibonacci {

    /**
     * <h3>使用Memorization(记忆法，也称备忘录)改进，时间复杂度为O(n)</h3>
     *
     * @param n 斐波拉契数列的索引，也可以说第n项
     * @return 第n项的值
     */
    // f(3) => 2 求第三项要调用5次递归，调用自己时直接取值的不算
    // f(4) => 4 求第三项要调用4次递归，调用自己时直接取值的不算
    // f(5) => 6 求第三项要调用7次递归，调用自己时直接取值的不算
    // f(n) = 2n - 4 => 时间复杂度为O(n)
    public static int fibonacci(int n) {
        if (n < 0){
            throw new IllegalArgumentException(
                    String.format("参数n: [%d] 不合法",n)
            );
        }
        int[] cache = initFibonacciArray(n + 1);
        return fibonacciAtn(n, cache);
    }

    /**
     * 根据第n项和cache数组（其中存放的是0……n的f(n)值）
     * @param n 第n项，在数列中的索引
     * @param cache 存放f(1)……f(n)的数组
     * @return 返回f(n)的值
     */
    private static int fibonacciAtn(int n, int[] cache) {
        if (cache[n] != -1){
            return cache[n];
        }
        int x = fibonacciAtn(n - 1, cache);
        int y = fibonacciAtn(n - 2, cache);
        cache[n] = x + y;
        return cache[n];
    }

    /**
     * 初始化记录f(1)……f(n)的数组
     * @param length 数组的长度
     * @return 初始化的数组
     */
    private static int[] initFibonacciArray(int length) {
        if (length == 1){
            return initFibonacciArray(2);
        }
        int[] arr = new int[length];
        Arrays.fill(arr, -1);
        arr[0] = 0;
        arr[1] = 1;
        return arr;
    }

    /**
     * 原始版的递归求斐波拉契数列n项，时间复杂度为⊖(1.618^n)
     * @param n 第n项
     * @return f(n)
     */
    // f(3) => 5 求第三项要调用5次递归
    // f(4) => 9 求第三项要调用9次递归
    // f(5) => 15 求第三项要调用15次递归
    // 2 * f(n + 1) - 1
    public static int fibonacciAtn(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int x = fibonacciAtn(n - 1);
        int y = fibonacciAtn(n - 2);
        return x + y;
    }

    public static void main(String[] args) {
        System.out.println(fibonacciAtn(8));
    }
}
